The Internet and other similar networks are currently being used to transmit and receive (e.g. transreceive) data. An example of transreceived data is the request and delivery of streaming media from a server device to a client device. For example, audio and/or video content from news broadcasts can be streamed, from a server device/devices, through a network to one or more client devices.
The terms “streaming media” and “streamed media”, as used herein, essentially mean real-time or near-real-time delivery of critical content (e.g., audio and/or video data) to a subscribing user's client device or devices. The client device/devices render the streamed media in a way that is appropriate for the client device and the media. By way of example, a live or previously recorded radio program can be transmitted as streamed audio data over a network to a wireless communication device, such as, e.g., a mobile telephone device, which then reproduces the audio signal.
To provide better service to the user, some networks that are used for streaming media are beginning to offer predictable levels of service. For example, in certain networks, an attempt is made to maintain both the throughput of the network connections (i.e., the data rate) and the errors introduced into data transmitted on those connections (i.e., the residual bit error rate or BER) within certain predicted limits, for the duration of a connection. An example of such a network is the so-called “third generation” (3G) wireless network. 3G wireless networks are being designed to support high data rate wireless telephone services. Streaming content services are predicted to be major applications in these and other types of networks. Such services will be required to deal with certain levels of BER while maintaining an acceptable streaming content experience for subscribing users. As such, in many of these networks there is a need for error correction services that reduce the amount of corrupted data.
Forward error correction (FEC) in packet networks is a well-known error correction technique to provide a mechanism by which a sending device provides a receiving device with additional FEC data that can be subsequently used by the receiving device to detect and correct errors in received data. Thus, to support FEC the sending device typically includes an FEC encoder and the receiving device typically includes an FEC decoder, each of which performs an aspect of FEC using Error Correction Codes (ECCs). ECCs are special codes extensively used in telecommunications for reliable data transmission over noisy channels. These codes increase the size of the transmitted data in such a way that modifications of transmitted data that are caused by noise in the data channel can be reverted on receiving end.
One kind of ECCs are FEC codes. FEC codes allow restoration of large portions of missed or damaged data when a recipient cannot request resending of data from the sender. A typical application is a cellular telephone. Even if the recipient's receiver is temporarily shadowed from the transmitter, such as when the cellular telephone is passing through a tunnel or going under a bridge, the use of FEC codes allows for a smooth playback using the data that is recovered from previously received packages.
A practical implementation of FEC codes is difficult because of the large number of clients that are supported by one retransmitting module. Each client requires a separate and independent encoding stream which can cause overloading of the retransmitting module's computational capacities.
On the receiving end, the use of FEC codes can prove to be difficult because the client receiver typically has a slower processor without the computational capacity that is required by data restoration algorithms. Efficient implementations of FEC codes are, therefore, important for telecommunications. Modem FEC code algorithms are most computationally intensive in encoding and decoding by multiplying matrices in a Galois field.
Some FEC code algorithms are implemented in hardware but are not adequate for general use because they are expensive and require hardware upgrades that increase the cost of ownership even further, often where impractical-such as in the replacement of existing cellular telephones. In that matrix multiplication in a Galois field requires the majority of total encoding and decoding processing time, in would be an advance in the art to devise an efficient implementation. Consequently, there is a need for improved methods, apparatuses, computer programs, and systems that can provide such a capability.
Some matrix multiplication algorithms are not applicable for operation in a Galois field. Still other algorithms are applicable to matrix multiplication in a Galois field but they are either so complicated that their practical usability is questionable (e.g. such as algorithms of Strassen-Winograd family), or they are targeted to be used only for special forms of matrixes such as tri-diagonal, five-diagonal, sparse, etc.